package euler.p051_100;

import java.util.Arrays;

import euler.MainEuler;
import euler.helper.NaturalHelper;

public class Euler070 extends MainEuler {
    /*
        Euler's Totient function, φ(n) [sometimes called the phi function],
        is used to determine the number of positive numbers less than or
        equal to n which are relatively prime to n.
        For example, as 1, 2, 4, 5, 7, and 8, are all less than nine
        and relatively prime to nine, φ(9)=6.
        The number 1 is considered to be relatively prime to
        every positive number, so φ(1)=1.

        Interestingly, φ(87109)=79180, and it can be seen
        that 87109 is a permutation of 79180.

        Find the value of n, 1 < n < 10^7, for which φ(n)
        is a permutation of n and the ratio n/φ(n) produces a minimum.

     */
    public String resolve() {

        int limite = 10000000;
        float minRatio = 10;
        int bestN = 0;

        for (int i = limite; i > 1; i--) {
            int phi = naturalHelper.phi(i);

            float div = ((float)i)/phi;
            if (div < minRatio && Arrays.equals(NaturalHelper.digitos(i,10,true), NaturalHelper.digitos(phi,10,true))) {
                minRatio = div;
                bestN = i;
            }
        }

        return String.valueOf(bestN);
    }
}
